// https://leetcode.cn/problems/add-one-row-to-tree/
// Created by ade on 2022/8/5.
//

/*
 *
给定一个二叉树的根 root 和两个整数 val 和 depth ，在给定的深度 depth 处添加一个值为 val 的节点行。

注意，根节点 root 位于深度 1 。

加法规则如下:

给定整数 depth，对于深度为 depth - 1 的每个非空树节点 cur ，创建两个值为 val 的树节点作为 cur 的左子树根和右子树根。
cur 原来的左子树应该是新的左子树根的左子树。
cur 原来的右子树应该是新的右子树根的右子树。
如果 depth == 1 意味着 depth - 1 根本没有深度，那么创建一个树节点，值 val 作为整个原始树的新根，而原始树就是新根的左子树。
 *
 * */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    TreeNode() : val(0), left(nullptr), right(nullptr) {}

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution {
public:
    vector<TreeNode *> heads;

    TreeNode *addOneRow(TreeNode *root, int val, int depth) {
        if (depth == 1) {
            TreeNode *tmp = new TreeNode(val);
            tmp->left = root;
            return tmp;
        }
        dfs(root, 0, depth - 1);
        for (auto item : heads) {
            if (item->left) {
                TreeNode *tmp = new TreeNode(val);
                TreeNode *tmpL = item->left;
                item->left = tmp;
                tmp->left = tmpL;
            } else {
                TreeNode *tmp = new TreeNode(val);
                item->left = tmp;
            }
            if (item->right) {
                TreeNode *tmp = new TreeNode(val);
                TreeNode *tmpR = item->right;
                item->right = tmp;
                tmp->right = tmpR;
            } else {
                TreeNode *tmp = new TreeNode(val);
                item->right = tmp;
            }
        }
        return root;
    }

    void dfs(TreeNode *node, int index, int depth) {
        if (!node) return;
        if (index == depth) {
            heads.push_back(node);
        }
        dfs(node->left, index + 1, depth);
        dfs(node->right, index + 1, depth);
    }

    TreeNode *init() {
        TreeNode *head1 = new TreeNode(1);
        TreeNode *head2 = new TreeNode(0);
        TreeNode *head3 = new TreeNode(1);
        TreeNode *head4 = new TreeNode(0);
//        TreeNode *head4 = new TreeNode(3);
//        TreeNode *head5 = new TreeNode(3);
//        TreeNode *head6 = new TreeNode(4);
//        TreeNode *head7 = new TreeNode(4);
        head1->right = head2;
//        head1->right = head3;
        head2->right = head3;
        head2->left = head4;
//
//        head3->left = nullptr;
//        head3->right = nullptr;
//        head4->left = head6;
//        head4->right = head6;
        return head1;
    }
};

int main() {
    Solution so;
    TreeNode *head = so.init();
    so.addOneRow(head);
    so.show(head);
    return 0;
}